﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<list>
#include<map>
#include<string>
#include<thread>
#include<time.h>
#include<functional>
#include<stack>
#include<mutex>
using namespace std;

#include<assert.h>

//int main()
//{
//	int a = 0;
//	int b = 1;
//	int* p = &a;
//
//	a + b;
//
//	// 左值引用给左值取别名
//	int& ref1 = a;
//
//	// 左值引用给右值取别名
//  //(a+b)返回的是一个临时变量，临时变量具有常性，因此这个左值引用不能给右值取别名，这是权限的放大
//	// int& ref2 = (a + b);
//  //加了const，是既可以引用左值，也可以引用右值
//	const int& ref2 = (a + b);
//
//	// 右值引用给右值取别名
//  //是右值是不能取地址的，但是给右值取别名后，会导致右值被存储到特定位置，且可
//  //以取到该位置的地址，也就是说例如：不能取字面量10的地址，但是ret3引用后，可以对ret3取地
//  //址，也可以修改ret3。如果不想ret3被修改，可以用const int&& ret3 去引用，
//  //这个了解一下实际中右值引用的使用场景并不在于此，这个特性也不重要。
//	int&& ref3 = (a + b);
//
//	// 右值引用不能给左值引用取别名，但右值引用给 move后左值取别名
//	//int&& ref4 = a; //no
//	int&& ref4 = move(a);
//
//	return 0;
//}


//void func(int& a)
//{
//	cout << "void func(int& a)" << endl;
//}
//
//void func(int&& a)
//{
//	cout << "void func(int&& a)" << endl;
//}
//
//int main()
//{
//	int a = 0;
//	int b = 1;
//	func(a);
//	func(a + b);
//	return 0;
//}

//int main()
//{
//	string s1("hello");
//	string s2("world");
//
//	string ret1 = s1;
//	string ret2 = s1 + s2;
//
//	return 0;
//}

//void Fun(int& x) { cout << "左值引用" << endl; }
//void Fun(const int& x) { cout << "const 左值引用" << endl; }
//void Fun(int&& x) { cout << "右值引用" << endl; }
//void Fun(const int&& x) { cout << "const 右值引用" << endl; }
//// 模板中的&&不代表右值引用，而是万能引用，其既能接收左值又能接收右值。
//// 模板的万能引用只是提供了能够接收同时接收左值引用和右值引用的能力，
//// 但是引用类型的唯一作用就是限制了接收的类型，后续使用中都退化成了左值，这样才能实现转移资源
//// 我们希望能够在传递过程中保持它的左值或者右值的属性, 就需要用我们下面学习的完美转发
//
////万能引用(引用折叠)：既可以引用左值，也可以引用右值
//template<typename T>
//void PerfectForward(T&& t)
//{
//	Fun(t);
//}
//int main()
//{
//	PerfectForward(10);// 右值
//	int a;
//	PerfectForward(a); // 左值
//	PerfectForward(std::move(a)); // 右值
//	const int b = 8;
//	PerfectForward(b);  // const 左值
//	PerfectForward(std::move(b)); // const 右值
//
//
//	return 0;
//}


//template <class ...Args>
//void ShowList(Args... args)
//{
//	cout << sizeof...(args) << endl;
//}
//
//int main()
//{
//	ShowList();
//	ShowList('x');
//	ShowList('x','y');
//	ShowList('x',1);
//
//	return 0;
//}
//
//void _ShowList()
//{
//	cout << endl;
//}
//
////如何解析出可变参数包呢
////递归推导思维
//template <class T, class ...Args>
//void _ShowList(const T& val, Args... args)
//{
//	cout << __FUNCTION__ << "(" << sizeof...(args) << ")" << endl;
//	//cout << val << " ";
//	_ShowList(args...);
//}
//
//template <class ...Args>
//void ShowList(Args... args)
//{
//	_ShowList(args...);
//}
//
//int main()
//{
//	ShowList();
//	ShowList(1);
//	ShowList(1, 'A');
//	ShowList(1, 'A', std::string("sort"));
//
//	return 0;
//}
//
//
//template <class T>
//int PrintArg(T t)
//{
//	cout << t << " ";
//
//	return 0;
//}
////展开函数
//template <class ...Args>
//void ShowList(Args... args)
//{
//	//int arr[] = { (PrintArg(args), 0)... };
//	int arr[] = { PrintArg(args)... };
//	cout << endl;
//}
//
////编译器编译推演生成了以下代码
//void ShowList(char a1, char a2, std::string a3);
//{
//	int arr[] = { PrintArg(a1), PrintArg(a2), PrintArg(s3) };
//	cout << endl;
//}
//int main()
//{
//	ShowList(1);
//	ShowList(1, 'A');
//	ShowList(1, 'A', std::string("sort"));
//	return 0;
//}


//STL容器的插入接口基本都有一个emplace系列



//lumbda是一个可调用对象，它模拟的是函数对象
//lunbda表达式

//int main()
//{
//	auto add1 = []()->void {cout << "省略了参数列表,()也可以省略" << endl;  };
//	//cout << add1() << endl; //err
//	//[]: 捕捉列表; (int x,int y):参数列表，无参可省略，括号也可省可不省； ->int:返回值类型；{}：括号里面是函数体
//	auto add = [](int x, int y)->int {return x + y; };
//	cout << add(1,2) << endl;
//
//	auto add2 = [](int x, int y)
//	{
//		return x + y;
//	};
//	cout << add2(3, 4) << endl;
//
//	cout << [](int x, int y)->int {return x + y; }(1,2) << endl;
//
//	return 0;
//}


//使用lumbda中的捕捉列表
//int main()
//{
//	//1.
//	//不能直接使用外面的x,y,lumbda只能用自己作用域内部的，x,y是传参来的
//	int x = 0, y = 1;
//	int m = 2, n = 3;
//
//	auto swap1 = [](int& rx, int& ry)
//	{
//		int tmp = rx;
//		rx = ry;
//		ry = tmp;
//	};
//
//	swap1(x, y);
//
//	cout << x << " " << y << endl;
//
//	//传值捕捉
//	//2.lumbda的作用域是独立的，如果不传参要使用x,y的话，需要捕捉上下文中的变量供lambda函数使用。
//	//捕捉过来的x和y是一个临时拷贝，就是一个形参，就相当于加了个cosnt，为了防止误用
//	//如果想要改变x和y，就需要加一个mutable(易变的)，可以修改传过来的值(形参)
//	//auto swap2 = [x,y]() mutable
//	//{
//	//	int tmp = x;
//	//	x = y;
//	//	y = tmp;
//	//};
//
//	//swap2();
//
//	//cout << x << " " << y << endl;
//
//
//	//3.引用捕捉
//	auto swap2 = [&x, &y]() mutable
//	{
//		int tmp = x;
//		x = y;
//		y = tmp;
//	};
//
//	swap2();
//	cout << x << " " << y << endl;
//
//	//4.混合捕捉
//	auto func1 = [&x, y]()
//	{
//		//...
//	};
//
//	//5.全部引用捕捉
//	auto func2 = [&]()
//	{
//		//...
//	};
//
//	//6.全部传值捕捉
//	auto func3 = [=]()
//	{
//		//...
//	};
//
//	//6.全部引用捕捉 除了x是传值捕捉
//	auto func4 = [&,x]()
//	{
//		//...
//	};
//
//	return 0;
//}

//
//线程库
//Pthreads 一般用于Unix-likePOSIX(Portable Operating System Interface可移植操作系统接口)系统，如：Linux..
//windowsOS没有选择支持POSIX接口，所以不能使用，而Linux选择的是支持POSIX接口
//Windows NT声明部分实现了POSIX标准，这部分可以使用
//Windows下提供了一套自己的实现线程的方法：Create Thread，为Win API方法
//
//int main()
//{
//	//问题：Linux下和windows线程不兼容；解决：C++98中，Linux 和 windows下都可以支持的多线程程序--条件编译
//	//封装2套线程方法
//	#ifdef _WIN32
//		CreateThread
//	#else
//		pthread_create
//	#endif
//
//	//C++11中，Linux 和 windows下都可以支持的多线程程序。--thread库
//	
//}
//
////创建一个线程 从1打印到10
//void Func(int n,int menber)
//{
//	for (int i = 0; i < n; ++i)
//	{
//		cout << menber << ":" << i << endl;;
//	}
//	cout << endl;
//}
//
//int main()
//{
//	//此时有3个线程，主线程和2个子线程，如果主线程提前结束，下面这两个子线程就崩了
//	thread t1(Func, 10, 1);
//	thread t2(Func, 20, 2);
//
//	t1.join();
//	t2.join();
//	return 0;
//}
//
//
//int main()
//{
//	int n1, n2;
//	cin >> n1 >> n2;
//	thread t1([n1](int menber)
//		{
//			for (int i = 0; i < n1; ++i)
//			{
//				cout << menber << ":" << i << endl;;
//			}
//			cout << endl;
//		}, 1);
//
//	thread t2([n2](int menber)
//		{
//			for (int i = 0; i < n2; ++i)
//			{
//				cout << menber << ":" << i << endl;;
//			}
//			cout << endl;
//		}, 2);
//
//	t1.join();
//	t2.join();
//	return 0;
//}


//要求m个线程分别打印n
//int main()
//{
//	size_t m;
//	cin >> m;
//	vector<thread> vthds(m);
//	//要求m个线程分别打印n
//	for (size_t i = 0; i < m; ++i)
//	{
//		size_t n = 10;
//		//cin >> n;
//
//		vthds[i] = thread([n, m]() {
//			for (size_t j = 0; j < n; ++j)
//			{
//				cout << this_thread::get_id() << ":" << j << endl;
//
//				this_thread::sleep_for(chrono::milliseconds(100));
//			}
//			cout << endl;
//			});
//	}
//
//	for (auto& t : vthds)
//	{
//		t.join();
//	}
//
//	//windows下支持的原子操作
//	// type __sync_val_compare_and_swap(type * ptr, type oldval, type newval, ...)
//	//Linux下支持的原子操作
//	// bool __sync_bool_compare_and_swap (type *ptr, type oldval, type newval, ...)
//
//	//非原子
//	int i = 0;
//	//i += 1;
//	
//	//原子操作
//	int old = i;
//	while (!__sync_bool_compare_and_swap(&i, old, old + 1))
//	{
//		old = i;
//	}
//	return 0;
//}

//lubda对象有多大  1byte
//int main()
//{
//	int x = 0, y = 1;
//	int m = 2, n = 3;
//
//	auto swap1 = [](int& rx, int& ry)
//	{
//		int tmp = rx;
//		rx = ry;
//		ry = tmp;
//	};
//
//	cout << sizeof(swap1) << endl;
//
//	return 0;
//}


////给线程加锁
//#include<mutex>
//mutex mtx;
//
//int x = 0;
//int y = 0;
//
//void Func(int n)
//{
//	//cout << &n << endl;
//	//cout << &x << endl;
//	//1.并行，大量时间都在加锁和解锁，还有切换上下文的消耗
//	//for (int i = 0; i < n; ++i)
//	//{
//	//	mtx.lock();
//	//	++x;
//	//	mtx.unlock();
//	//}
//	 
//	
//	//串行
//	//2.次情况下第二种效率比第一种高
//	mtx.lock();
//	for (int i = 0; i < n; ++i)
//	{
//		++x;
//	}
//	mtx.unlock();
//}
//
//int main()
//{
//	int n = 10000000;
//	size_t begin = clock();
//	thread t1(Func, n);
//	thread t2(Func, n);
//
//	t1.join();
//	t2.join();
//	size_t end = clock();
//
//	cout << x << endl;
//	cout << end - begin << endl;
//	return 0;
//}


//给线程加锁
//#include<mutex>
//mutex mtx;
//int x = 0;
//
//list<int> lt;
//
//void Func(int n)
//{
//	//cout << &n << endl;
//	//cout << &x << endl;
//	//1.并行，大量时间都在加锁和解锁，还有切换上下文的消耗
//	//for (int i = 0; i < n; ++i)
//	//{
//	//	mtx.lock();
//	//	++x;
//	//	lt.push_back(x);	
//	//	//cout << x << endl;
//	//	mtx.unlock();
//
//	//	cout << i << endl;
//	//	cout << i << endl;
//	//	cout << i << endl;
//	//}
//
//
//	//串行 
//	//2.此情况下第二种效率比第一种高，加了打印后，两种方案效率差不多
//	mtx.lock();
//	for (int i = 0; i < n; ++i)
//	{
//		++x;
//		lt.push_back(x); 
//		//cout << x << endl;
//
//		cout << i << endl;
//		cout << i << endl;
//		cout << i << endl;
//	}
//	mtx.unlock();
//
//}
//
//int main()
//{
//	int n = 10000;
//	size_t begin = clock();
//	thread t1(Func, n);
//	thread t2(Func, n);
//
//	t1.join();
//	t2.join();
//	size_t end = clock();
//
//	cout << x << endl;
//	cout << end - begin << endl;
//	return 0;
//}
//
//
//#include<mutex>
// 
//int main()
//{
//	int n = 1000000;
//	int x = 0;
//	mutex mtx;
//	size_t begin = clock();
//
//	thread t1([&, n]() {
//		mtx.lock();
//		for (int i = 0; i < n; ++i)
//		{
//			++x;
//		}
//		mtx.unlock();
//		});
//
//	thread t2([&, n]() {
//		mtx.lock();
//		for (int i = 0; i < n; ++i)
//		{
//			++x;
//		}
//		mtx.unlock();
//		});
//
//	t1.join();
//	t2.join();
//	size_t end = clock();
//
//	cout << x << endl;
//	cout << end - begin << endl;
//	return 0;
//}

//int x = 0;
////递归互斥锁：如果发现是自己锁自己就不处理
//recursive_mutex mtx;
////mutex mtx;
//
//void Func(int n)
//{
//	if (n == 0)
//		return;
//
//	mtx.lock();
//	++x;
//	//mtx.unlock(); ok
//	Func(n - 1);
//	//mtx.unlock(); no
//	mtx.unlock(); 
//}
//
//int main()
//{
//	thread t1(Func, 10000);
//	thread t2(Func, 20000);
//
//	t1.join();
//	t2.join();
//
//	cout << x << endl;
//	return 0;
//}

//template<class Lock>
//class LockGuard
//{
//public:
//	LockGuard(Lock & lk)
//		:_lk(lk)
//	{
//		_lk.lock();
//	}
//
//	~LockGuard()
//	{
//		_lk.unlock();
//	}
//
//private:
//	Lock& _lk;
//};
//
//
//int x = 0;
////递归互斥锁：如果发现是自己锁自己就不处理
//mutex mtx;
//
//void Func(int n)
//{
//	for (int i = 0; i < n; ++i)
//	{
//		try
//		{
//			//mtx.lock();
//			//LockGuard<mutex> lock(mtx);
//			//库里面有lock_guard
//			lock_guard<mutex> lock(mtx);
//
//			++x;
//			//抛异常,抛异常是直接跳到catch的地方
//			if (rand() % 3 == 0)
//			{
//				throw exception("抛异常");
//			}
//			//mtx.unlock();
//		}
//		catch (const exception& e)
//		{
//			cout << e.what() << endl;
//		}
//	}
//}
//
//int main()
//{
//	thread t1(Func, 10);
//	thread t2(Func, 20);
//
//	t1.join();
//	t2.join();
//
//	cout << x << endl;
//	return 0;
//}

//atomic 原子
 
//void Func(int x)
//{
//	cout << x << endl;
//}
//
//int main()
//{
//	int n = 100000;
//	//atomic<int> x = 0;
//	//atomic<int> x = { 0 };
//	atomic<int> x{ 0 };
//	//mutex mtx;
//	size_t begin = clock();
//
//	thread t1([&, n]() {
//		for (int i = 0; i < n; ++i)
//		{
//			++x;
//		}
//		});
//
//	thread t2([&, n]() {
//		for (int i = 0; i < n; ++i)
//		{
//			++x;
//		}
//		});
//
//	t1.join();
//	t2.join();
//	size_t end = clock();
//
//	cout << x << endl;
//	cout << end - begin << endl;
//
//	//Func(x);
//	printf("%d\n", x.load());
//
//	return 0;
//}

////2个线程交替打印，一个打印奇数，一个打印偶数
////条件变量
//#include<condition_variable>
//
//int main()
//{
//	mutex mtx;
//	condition_variable cv;
//
//	int n = 100;
//	int x = 1;
//
//	//问题1：如何保证t1先运行，t2阻塞
//	//问题2：如何防止一个线程一直运行
//	//为什么要放置一个线程连续打印？
//	//假设t1先获取到锁，t2后获取到锁，t2阻塞在锁上面
//	//然后t1打印计数，++x,x变成偶数
//	//t1 notify,但是没有线程wait
//	//t1 lock除了作用解锁，t1时间片到了，切出去了
//	//t2获取到锁，打印，notify ，但是灭意线程等待
//	//lock出作用域，解锁
//	//假设t2的时间片重组，再次获取到锁，如果没有条件控制就会导致t2连续打印
//	thread t1([&, n]() {
//			while(1)
//			{
//				unique_lock<mutex> lock(mtx);
//				if (x >= 100)
//					break;
//
//				//if (x % 2 == 0)
//				//{
//				//	cv.wait(lock);
//				//}
//
//				cv.wait(lock, [&x]() {return x % 2 != 0; });
//
//				cout << this_thread::get_id() << ":" << x << endl;
//				++x;
//
//				cv.notify_one();
//			}
//		});
//
//	thread t2([&, n]() {
//			while (1)
//			{
//				unique_lock<mutex> lock(mtx);
//				if (x >= 100)
//					break;
//
//				//if (x % 2 == 1)
//				//{
//				//	cv.wait(lock);
//				//}
//
//				cv.wait(lock, [&x]() {return x % 2 == 0; });
//
//				cout << this_thread::get_id() << ":" << x << endl;
//				++x;
//
//				cv.notify_one();
//			}
//		});
//
//	t1.join();
//	t2.join();
//
//	return 0;
//}

////包装器--头文件function--使用方法如下
////class function<Ret(Args...)>;
////Ret:被调用函数的返回类型
////Args...:被调用函数的形参
//
//#include<functional>
//
//int f(int a, int b)
//{
//	cout << "int f(int a,int b)" << endl;
//	return a + b;
//}
//
//struct Functor
//{
//public:
//	int operator() (int a, int b)
//	{
//		cout << "int operator() (int a, int b)" << endl;
//
//		return a + b;
//	}
//};
//
//class Plus
//{
//public:
//	Plus(int rate = 2)
//		:_rate(rate)
//	{}
//	
//	static int plusi(int a, int b)
//	{
//		return a + b;
//	}
//
//	double plusd(double a, double b)
//	{
//		return a + b * _rate;
//	}
//
//private:
//	int _rate = 2;
//};
//
//
//int main()
//{
//	//int(*pf1)(int, int) = f;
//	//map<string, >
//
//	//函数名（函数指针）
//	function<int(int, int)> f1 = f;
//	cout << f1(1, 2) << endl;
//	//函数对象
//	function<int(int, int)> f2 = Functor();
//	cout << f2(10, 20) << endl;
//	//lembda表达式
//	function<int(int, int)> f3 = [](int a, int b) {
//		cout << "[](int a, int b) {return a+b;}" << endl;
//		return a + b; 
//	};
//	cout << f3(100, 200) << endl;
//
//
//	//function<int(int, int)> f4 = &Plus::plusi; 
//	//类的成员函数
//	function<int(int, int)> f4 = Plus::plusi;
//	cout << f4(1, 2) << endl;
//
//	//非静态成员函数要加&，静态成员函数加上也可以
//	function<double(Plus, double, double)> f5 = &Plus::plusd;
//	cout << f5(Plus(), 10.5, 20.4) << endl;
//
//	Plus p5(3);
//	cout << f5(p5, 100.1, 200.3) << endl;
//
//	map<string, function<int(int, int)>> opFuncMap;
//	opFuncMap["函数指针"] = f;
//	opFuncMap["仿函数"] = Functor();
//	opFuncMap["lambda"] = [](int a, int b) {
//		cout << "[](int a, int b) {return a + b;}" << endl;
//		return a + b;
//	};;
//
//	cout << opFuncMap["lambda"](1, 6) << endl;
//
//	return 0;
//}

//#include<stack>
//#include<functional>
//#include<vector>
//
//
//
////函数
//int sub(int x, int y)
//{
//    return x - y;
//}
//
////仿函数
//struct mul
//{
//    int operator()(int x, int y)
//    {
//        return x * y;
//    }
//};
//
////使用包装器后
//class Solution {
//public:
//    int evalRPN(vector<string>& tokens) {
//        stack<int> st;
//        map<string, function<int(int, int)>> opFuncMap =
//        {
//            {"+",[](int a, int b) {return a + b; }},
//            {"-", sub}, //函数指针
//            {"*",mul()}, //仿函数
//            {"/",[](int a, int b) {return a / b; }}
//        };
//
//        for (auto& str : tokens)
//        {
//            if (opFuncMap.count(str))
//            {
//                int right = st.top();
//                st.pop(); 
//                int left = st.top();
//                st.pop();
//
//                st.push(opFuncMap[str](left, right));
//            }
//            else
//            {
//                st.push(stoi(str));
//            }
//        }
//        return st.top();
//    }
//};
//
//int main()
//{
//    vector<string> v;
//    Solution().evalRPN(v);
//    return 0;
//}



////绑定--bind
////调整参数顺序
//void Print(int a, int b)
//{
//	cout << "Print(int a, int b)" << endl;
//	cout << a << " ";
//	cout << b << endl;
//}
// 
//int main()
//{
//	Print(10, 20);
//
//	//调整参数的位置
//	//包含形如_n的名字，其中n是一个整数，这些参数是“占位符”，表示它们占据了传递给newCallable的参数的“位置”。
//	//auto RPrint = bind(Print, placeholders::_2, placeholders::_1);
//	function<void(int, int)>RPrint = bind(Print, placeholders::_2, placeholders::_1);
//	RPrint(10, 20);
//	
//	return 0;
//}
// 
//
//
////bind -- 调整参数个数
//class Sub
//{
//public:
//	Sub(int rate)
//		:_rate(rate)
//	{}
//
//	int func(int a, int b)
//	{
//		return (a - b) * _rate;
//	}
//private:
//	int _rate;
//};
//
//class Solution {
//public:
//    int evalRPN(vector<string>& tokens) {
//        stack<int> st;
//        map<string, function<int(int, int)>> opFuncMap =
//        {
//            {"+",[](int a, int b) {return a + b; }},
//            {"-",[](int a, int b) {return a - b; }},
//            {"*",[](int a, int b) {return a * b; }},
//            {"&",bind(&Sub::func,Sub(3),placeholders::_1,placeholders::_2)}
//        };
//
//        for (auto& str : tokens)
//        {
//            if (opFuncMap.count(str))
//            {
//                int right = st.top();
//                st.pop();
//                int left = st.top();
//                st.pop();
//
//                st.push(opFuncMap[str](left, right));
//            }
//            else
//            {
//                st.push(stoi(str));
//            }
//        }
//        return st.top();
//    }
//};
//int main()
//{
//    //调整参数个数
//    function<int(Sub, int, int)> fSub = &Sub::func;
//    cout << fSub(Sub(3), 10, 20) << endl;
//
//    function<int(int, int)> fSub1 = bind(&Sub::func, Sub(3), placeholders::_1, placeholders::_2);
//    cout << fSub1(10, 20) << endl;
//
//    function<int(Sub, int)> fSub2 = bind(&Sub::func, placeholders::_1, 100, placeholders::_2);
//    cout << fSub2(Sub(3), 20) << endl;
//	return 0;
//}

 